1. Field of the Invention
The present invention relates to the field of storage subsystem control and in particular to paging techniques applied to mapping in dynamically addressed virtual storage subsystems.
2. Discussion of Related Art
Typically, a computer stores data within devices such as hard disk drives, floppy drives, tape, compact disk, etc. These devices are otherwise known as storage devices. If a large amount of data requires storage, then a multiple of these devices are connected to the computer and utilized to store the data. A computer typically does not require knowledge of the number of storage devices that are being utilized to store the data because another device, the controller, is utilized to control the transfer of data to and from the computer to the storage devices. The software within the controller may be sophisticated to configure the storage devices to appear as one large "virtual" storage device to the computer. For example, three one megabyte hard disk drives can appear to the computer as one three megabyte virtual storage device. Similarly a plurality of disk drives, or a mix of storage devices such as a floppy disk, disk drive, solid state disk, or tape, can appear to the host as a single virtual storage device. The controller and the storage devices are typically called a storage subsystem and the computer is usually called the host because the computer initiates the requests for data from the storage devices.
Furthermore in a virtual storage device, the amount of physical storage can increase by adding storage devices to the storage subsystem. The host, however, continues to be unaware the storage subsystem comprises various storage devices or the amount of physical space available on each storage device. The host is, however, interested in the additional logical space available for its use.
Once data is stored within a storage device, the computer does not know the actual physical location of the data. Instead, the computer relies upon the controller to keep track of the physical location, that is, address of the data within the storage devices. The computer prefers to use virtual or "logical" addresses to determine the location of the data within the virtual storage device. These logical addresses are mapped, or translated into the actual physical addresses of the data within the storage device.
As previously stated, the storage subsystem controller, within the storage subsystem, manages the transfer of data within the storage devices in the storage subsystem as well as the mapping from host supplied virtual or logical addresses to physical storage locations. As taught in the art, the storage subsystem controller maintains an "in-core" map or look-up table in the storage subsystem controller, translating host logical addresses to physical storage.
A log structured storage system is one type of mapped virtual storage subsystem. In a log structured storage system, blocks of information within the storage system are represented as a log structure. These blocks are updated by appending the modified blocks to the log. As blocks of information are updated (e.g. modified), the modified blocks and information regarding the physical location of the modified blocks within the storage subsystem are appended to the log in a sequential order. Unlike other virtual storage systems, the storage subsystem controller determines the physical locations that are mechanically or electronically convenient, rather than locations that may be computationally derived from the logical address used by the host.
A log structured storage system improves write performance of the disk storage subsystem due to the reduction in write operations. Write requests tend to be random or scattered across a storage subsystem. The log structured storage system coalesces such scattered write requests into a single larger write request thereby eliminating multiple write operations to the disk array.
A segment buffer is an area in cache utilized to accumulate (e.g. coalesce) the write requests. Each write request is appended in sequential order to the last block within the segment buffer. The segment buffer allows the modified data blocks to be posted to disk as a single write operation when the segment buffer is full. The storage subsystem controller keeps track of the physical addresses of the blocks of information in an "in-core" map that locates the physical address associated with each logical address.
Since every host access to logical addresses in the storage subsystem requires the virtual storage subsystem to reference the in-core map, subsystem performance may be impacted by overhead processing to access the map to translate virtual (logical) addresses to physical addresses in the subsystem. Typically, the in-core map is located within cache or high-speed memory (e.g. high-speed cache) on the storage controller to improve access to the map. Storing the entire map in cache, however, requires an inordinate amount of relatively expensive cache memory. For example, if a disk array or logical unit has a capacity of 100 gbytes and a block size of 1 kbytes, the directory requires 100 gbytes 1 kbyte or 100 M entries. Assuming further that the directory occupies 32 bits for each entry, then 400 Mbytes of cache are required for the directory. This amount of cache is not only expensive but requires a large amount of physical space that may not be available within the controller.
From the above discussion, it is evident that a need exists to provide methods and associated apparatus for reducing the size of memory requirements to store a virtual to physical map in a virtually mapped storage subsystem while maintaining acceptable performance levels in the subsystem.